package leetcode_day._2021._202104._0110;

/**
 * @author yzh
 * @date 2021/4/7 8:32
 * 搜索旋转排序数组 II
 * 思路：
 *   给出的数组是经过翻转后的数组，数组原先是顺序排列
 *   使用顺序查找，数组不需要排序
 *   这道题跟 33 题的差别是这道题目中的数组元素是重复的
 *   如果 nums[low] == nums[mid]，那么不知道哪边是有序的
 *   所以遇到这种情况，直接 low++
 *   其他做法跟 33 的一样
 *
 */
public class _07_81 {

    public boolean search(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) return true;
        }
        return false;
    }

    public boolean search_perfect(int[] nums, int target) {
        int low = 0, high = nums.length - 1;
        while (low <= high) {
            int mid = (low + high) >> 1;
            if (target == nums[mid]) return true;
            if (nums[mid] == nums[low]) {
                ++low;
                continue;
            }
            if (nums[mid] >= nums[low]) {
                if (target >= nums[low] && target < nums[mid]) high = mid - 1;
                else low = mid + 1;
            } else {
                if (target > nums[mid] && target <= nums[high]) low = mid + 1;
                else high = mid - 1;
            }
        }
        return false;
    }
}
